1. Field of the Invention
The present invention relates to the field of vector quantization. Specifically, the present invention relates to a technique which increases the performance of vector quantization for applications such as speech recognition and computer graphics.
2. Background Information
Many modern applications, such as speech recognition and video compression, require algorithms that process large sets of vectors. In some instances, these vectors may be sampled from audio signals containing speech for speech recognition applications or red-green-blue (RGB) color intensity values for computer graphics applications. It is not always possible in certain applications to represent full fidelity of this input signal or vector. A 24-bit color image may not be able to be displayed on an 8-bit display, for example. In this example, a color map is used wherein vectors for each of the RGB color values are quantized to map to colors which may be displayed upon the 8-bit display. Therefore, in this case, a table of 256 "quantized" vectors (VQ's) is chosen to represent the color vector space. Each color vector is matched with its closest neighbor in the VQ table and stored using a table index. This type of vector quantization is known as a nearest-neighbor technique.
Vector quantization requires efficient searching techniques. One of the most prevalent types of algorithms used in prior art vector quantization techniques is known as the nearest neighbor or Voronoi class of vector quantizers. These quantizers simply compute the distance from each input vector being quantized and a quantized vector or VQ in a "codebook" or table containing VQ's. The vector being quantized is then encoded as the VQ which is closest. This technique tends to be more or less accurate (although it docs incur some loss in fidelity of the input vector), however, it requires that an entire codebook be searched prior to deciding which VQ is closest to the input vector. Therefore, these techniques are not very efficient and significant processing time is consumed because the entire codebook must be searched every time a vector is quantized.
More efficient algorithms divide the VQ codebook into many smaller codebooks. Given an input vector, these algorithms select progressively smaller tables in a "tree" which have the closest VQ to the vector being encoded. These types of quantizers are known as "tree-searched vector quantizers" or TSVQ's. The search narrows at each branch of the tree to smaller and smaller tables until a terminal node or "leaf" in the tree is reached. Upon reaching a leaf in the tree which may have several VQ's associated with it, the nearest neighbor to the vector being quantized is then determined for encoding. The effective search time using such a TSVQ can be reduced at most by a factor of the number N of children at each branch in the tree for each level in the tree over standard Voronoi search methods. If the tree has m levels, the greatest improvement is N.sup.m.
Notwithstanding faster search algorithms employed through the use of TSVQ's, vector quantization still requires that a set of quantized vectors be searched to determine which of the quantized vectors is closest to the input vector for coding. Even TSVQ's require that each VQ in the terminal nodes be scanned in order to determine the closest VQ to the input vector. Thus, if each leaf or terminal node contains ten quantized vectors, a search of all ten VQ's is required to be performed to determine which is closest to the input vector. Depending upon operating circumstances, searches of all VQ's may take lengthy periods of time and degrade the performance of a vector quantizer encoding an input signal. Thus, more efficient vector quantizers which use more efficient search techniques are desired.